package com.easy.carl.algorithm.String;

/**
 * 151. 翻转字符串里的单词
 */
public class ReverseWords151 {
    public String reverseWords1(String s) {
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        int left = chars.length - 1;
        int right = chars.length - 1;
        while (left >= 0) {
            System.out.println(chars[left]);
            //当前索引位置上是空
            if (chars[left] == ' ' && left + 1 < chars.length && chars[left + 1] != ' ') {
                if (sb.length() != 0) {
                    sb.append(" ");
                }
                if (left + 1 < chars.length && chars[left + 1] != ' ') {
                    sb.append(chars, left + 1, right - left);
                }
            } else {
                //当前索引位置上不是空，当前索引的下一个索引位置上是空，更新right索引
                if (left + 1 < chars.length && chars[left + 1] == ' ') {
                    right = left;
                }
                if (left == 0 && chars[left] != ' ') {
                    if (sb.length() != 0) {
                        sb.append(" ");
                    }
                    sb.append(chars, left, right - left + 1);
                }
            }
            left--;
        }
        return sb.toString();
    }

    public String reverseWords(String s) {
        s = replaceEmptyStr(s);
        char[] chars = s.toCharArray();
        reverseArray(chars, 0, chars.length - 1);
        //慢指针
        int slow = 0;
        //快指针
        int quick = 0;
        while (quick < chars.length) {
            //找到空字符时，则翻转
            if (chars[quick] == ' ') {
                reverseArray(chars, slow, quick - 1);
            } else {
                //当前字符不是空，前一个是空或者前一个索引为0时，重置慢指针
                if (quick == 0 || chars[quick - 1] == ' ') {
                    slow = quick;
                }
                //快指针到结尾，直接翻转
                if (quick == chars.length - 1) {
                    reverseArray(chars, slow, quick);
                }
            }
            quick++;
        }
        return String.valueOf(chars);
    }


    /**
     * 去除头尾及中间多余的空字符串
     *
     * @param s
     * @return
     */
    public String replaceEmptyStr(String s) {
        char[] chars = s.trim().toCharArray();
        int slow = 0;
        int quick = 0;
        while (quick < chars.length) {
            if (chars[quick] == ' ') {
                if (chars[quick - 1] != ' ') {
                    chars[slow++] = chars[quick];
                }
            } else {
                chars[slow++] = chars[quick];
            }
            quick++;
        }
        return String.valueOf(chars, 0, slow);
    }

    /**
     * 翻转字符串指定位置
     *
     * @param chars
     * @param start
     * @param end
     */
    public void reverseArray(char[] chars, int start, int end) {
        while (start < end) {
            char c = chars[start];
            chars[start] = chars[end];
            chars[end] = c;
            start++;
            end--;
        }
    }


    public static void main(String[] args) {
        ReverseWords151 reverseWords151 = new ReverseWords151();
        System.out.println(reverseWords151.reverseWords("  Bob    Loves  Alice   "));
    }
}
